Lời giải thứ nhất của bài toán 11 hậu khi tìm bằng giải thuật đệ quy và quay lui trong mục này. Đối xứng với lời giải bên dưới.Lời giải thứ 2680 của bài toán 11 hậu khi tìm bằng giải thuật đệ quy và quay lui trong mục này. Đối xứng với lời giải thứ nhất.

Trong giải thuật này, mỗi lời giải được ký hiệu bằng một mảng solution[1..n], trong đó solution[i]= j là cột mà quân hậu ở hàng thứ i đứng. Theo tính chất số học của các ô trên bàn cờ n x n, các ô trên các đường chéo cộng chứa ô (i, j) đều có tổng chỉ số hàng với chỉ số cột bằng i+j. Tổng này nhận các giá trị từ 2 đến 2n nên ta đánh số các đường chéo này từ 1 đến 2n-1. Như vậy các ô trên đường chéo cộng thứ nhất có tổng chỉ số dòng và cột là 2, các ô trên đường chéo thứ k có tổng ấy là k+1. Ta dùng một mảng Boolean Ok_plus[1..2n-1] để ký hiệu trạng thái đã có quân hậu nào trên đường chéo cộng thứ k chưa, nghĩa là Ok_plus[k]=True nếu đã có một quân hậu đứng chiếm giữ đường chéo cộng thứ k. Tương tự, các ô trên một đường chéo trừ có hiệu như nhau. Hiệu này nhận giá trị từ 1-n đến n- 1. Đánh số từ 1 đến 2n-1 từ đường chéo có hiệu chỉ số dòng trừ chỉ số cột là 1-n đến đường chéo có hiệu ấy bằng n-1. Khi đó đường chéo trừ thứ k có hiệu chỉ số dòng trừ chỉ số cột là k-n. Ta cũng dùng mảng ok_minus[1..2n-1] để chỉ trạng thái của các đường chéo này.

Giải thuật này cố gắng đặt quân hậu ở dòng thứ i vào cột nào đó, bắt đầu từ dòng thứ nhất (luôn có thể đặt được). Nếu ở dòng thứ i ta đặt quân hậu vào cột thứ j, thì nó khống chế tất cả các ô trong cột thứ j, đường chéo cộng thứ i+j-1, đường chéo trừ thứ i-j+n. Nếu có thể đặt được quân hậu ở dòng i và i = n ta có một lời giải. Nếu đặt được và i < n ta tiếp tục cố gắng đặt quân hậu tiếp theo vào dòng thứ i+1. Nếu không đặt được, ta quay lại nhấc quân hậu ở dòng thứ i-1 và tìm phương án tiếp theo của dòng thứ i-1.

• Nhận xét: trong hai lời giải ở hình bên các vị trí của quân hậu trên bàn cờ đứng theo vị trí nước đi của quân ngựa

Mã giả

Procedure Try_row(i)For j=1 To n doIf not ok_row(i) And not ok_col(j) And not ok_plus(i+j-1) And not ok_minus(i-j+n) then{solution(i)=j;ok_col(j)=True;ok_plus(i+j-1)=True;ok_minus(i-j+n)=True;If i<n thentry_row(i+1)ELSE print_solution();ok_row(i)=False;ok_col(j)=False;ok_plus(i+j-1)=False;ok_minus(i-j+n)=False;

}

Thủ tục tìm tất cả các lời giải của bài toán n hậu chỉ bao gồm một lời gọi Try_row(1):

Procedure n_queen(n);Call Try_row(1);

Cây tìm kiếm trong giải thuật

Cố gắng không thành công.Cây tìm kiếm lời giải với n=4.

Ta minh họa quá trình tìm kiếm lời giải cho bài toán n hậu với n = 4 trong hình bên. Ở trạng thái xuất phát, trên dòng 1 có 4 lựa chọn cho quân hậu: quân hậu thứ nhất có thể đứng ở các cột 1, 2, 3, 4. Nếu lựa chọn ô (1, 1), ở dòng thứ hai chỉ còn hai lựa chọn là cột 3 và cột 4. Nếu lựa chọn cột 3, trên dòng thứ 3 sẽ không còn ô nào không bị khống chế (ô (3, 1) và (3, 3) bị khống chế bởi (1, 1), ô (2, 3) và (3, 4) bị khống chế bởi (2, 3). Ta loại bỏ phương án chọn ô (2, 3) này và xét tiếp phương án chọn ô (2, 4). Khi lựa chọn ô (2, 4) ta cũng chỉ đặt thêm được một quân hậu ở dòng thứ ba. Dòng thứ tư lại không thể đặt bất kỳ quân hậu nào. Do đó ta lùi lại dòng thứ nhất, xét khả năng tiếp theo (1, 2), ta lần lượt được dãy các ô (1, 2), (2, 4), (3, 1), (4, 3). Tiếp tục với ô (1, 3), (1, 4). Chỉ có hai đường đi từ gốc tới lá với độ dài 4 nên bài toán 4 hậu chỉ có 2 lời giải thể hiện trên cây bằng các đường đi màu xanh lục.